//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,2,2,1]
//输出：true
// 
//
// 示例 2： 
// 
// 
//输入：head = [1,2]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目在范围[1, 10⁵] 内 
// 0 <= Node.val <= 9 
// 
//
// 
//
// 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
//
// Related Topics 栈 递归 链表 双指针 👍 2101 👎 0


//leetcode submit region begin(Prohibit modification and deletion)



/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
//        //第1种解法.
//        //1.找中间节点 leetcode 876
//        //2. 中间点后半个链表反转 leetcode 206
//        //3. 反转后链表与新链表逐一比较
//        ListNode middleNode = middleNode(head);
//        ListNode newListHead = reverseList(middleNode);
////        System.out.println(middleNode.val);
////        System.out.println(newListHead.val);
//        while(newListHead != null){
//            if(newListHead.val != head.val) {
//                return false;
//            }else{
//                newListHead = newListHead.next;
//                head = head.next;
//            }
//        }
//        return true;

        //第2种解法
        //1.找中间点的同时反转前半个链表
        //2. 反转后的前半个链表与中间点开始的后半个链表逐一比较
        //（把第一种解法合并起来，再做优化）
        ListNode p1 = head;//慢指针
        ListNode p2 = head;//快指针
        ListNode n1 = null;//这是新链表的头，初始化为空
        ListNode o1 = head;
        while(p2 != null && p2.next != null){
            p1 = p1.next;
            p2 = p2.next.next;
            //反转链表
            o1.next = n1;
            n1 = o1; //当前链表的节点使用当前旧链表的节点
            o1 = p1; //旧链表前移，因为慢的针p1已经向前移动了，o1指与p1一样就可以了
        }
        //奇数节点慢指针需要再前前走一步
        if(p2 != null){
            p1 = p1.next;
        }
        //此时p1就是中间点,n1为新链表的头
        while(n1 != null){
            if(n1.val != p1.val){
                return false;
            }
            n1 = n1.next;
            p1 = p1.next;
        }
        return true;

    }

    //链表反转 leetcode 206
    private ListNode reverseList(ListNode head){
//        //第一种
////        执行耗时:7 ms,击败了40.89% 的Java用户
////        内存消耗:56.3 MB,击败了74.13% 的Java用户
//        if(head == null || head.next == null){
//            return head;
//        }
//        ListNode newListHead = null;//新链表首次初始化为空
//        ListNode pointer = head;//旧链表指针
//        while (pointer != null){
//            newListHead = new ListNode(pointer.val, newListHead);
//            pointer = pointer.next;//旧链表指针后移
//        }
//        return newListHead;

        //第2种
//        执行耗时:5 ms,击败了65.32% 的Java用户
//        内存消耗:58 MB,击败了68.09% 的Java用户
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    //leetcode 876
    private ListNode middleNode(ListNode head){
        ListNode p1 = head;//慢
        ListNode p2 = head;//快指针
        while (p2 != null && p2.next != null){
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
